\documentclass[12pt]{article}
\usepackage{calc,fancyhdr}
\usepackage[hmargin=.5in,vmargin=.75in,
            footskip=.25in,headsep=.5in-\headheight]{geometry}

% Template solution to Exercise 5.

% Common formatting macros for CSC165.
\usepackage{amsmath,amssymb}
\input{macros-165}

% Page layout: stretch text to fill up page.
\flushbottom

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{CSC\,165\,H1S}
\chead{Homework Exercise \#\,8}
\rhead{Winter 2014}

\begin{document}

\begin{large}
  \noindent
  Name: Robert Staskiewicz \hfill CDF login name: c3staski\\[0.5cm]
  Partner: Ekam Shahi    \hfill CDF login name: c3shahie
\end{large}

\medskip

\noindent
\rule{\textwidth}{.5pt}

\subsection*{Topic: Asymptotic Analysis}

\medskip

\begin{enumerate}
 
       
    % place solution to question 1 below

    \item
    \begin{enumerate}
	\item 
    \medskip
    \noindent
    Consider the following definition of $\mathcal{O}$:
    \begin{quote}
    $\exists c \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies (n^a\leq cn^b)$
    \end{quote}
    {\bf Proof:} 
    \begin{pindent}
    	Let $c' = 1$ Then $c' \in \R^+$\\
    	let $B'=1,$ Then $B' \in \N$\\

        \begin{assumption}{$(n\in \N) \land (n \geq B')$}
		Then $ n^a\leq c'(n^b)$\just{ Substitution  } \\
		Then $ n^a\leq 1(n^b)$\\
		Then $ n^a\leq n^b $ \just{$(n\geq 1)\land(b\geq a)$} \just{Monotonically increasing on $n\geq 1$ }
        \end{assumption}
        Then $\forall n \in \N, (n\geq B') \implies (n^a\leq c'n^b) $ \\
        Therefore we showed for an arbitrary $(B'\land c')$ that we have an upper bound.\\
        Then $\exists c \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies (n^a\leq cn^b)$
        
        % $ \ \forall n \in \Z,\ \sum_{1}^{i} (2n-1) \equiv n^2  $
    \end{pindent}
    \medskip
    
    % place solution to question 2 below
    
    	\item 
        \medskip
        \noindent
        Consider the following definition of $\mathcal{O}$:
        \begin{quote}
        $\exists c \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies (a^n\leq cb^n)$
        \end{quote}
        {\bf Proof:} 
        \begin{pindent}
        	Let $c' = 1$ Then $c' \in \R^+$\\
        	let $B'=1,$ Then $B' \in \N$\\
    
            \begin{assumption}{$(n\in \N) \land (n \geq B')$}
    		Then $ a^n\leq c'(b^n)$\just{ Substitution  } \\
    		Then $ a^n\leq 1(b^n)$\\
    		Then $ a^n\leq b^n $ \just{$(n\geq 1)\land(b\geq a)$} \just{Monotonically increasing on $n\geq 1$ }
            \end{assumption}
            Then $\forall n \in \N, (n\geq B') \implies (a^n\leq c'b^n) $ \\
            Therefore we showed for an arbitrary $(B'\land c')$ that we have an upper bound.\\
            Then $\exists c \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies (a^n\leq cb^n)$
            
            % $ \ \forall n \in \Z,\ \sum_{1}^{i} (2n-1) \equiv n^2  $
        \end{pindent}
        \medskip
    
        	\item 
            \medskip
            \noindent
            Consider the following definition of $\Theta$:
            \begin{quote}
            $${\exists c_1\in \R^+,\exists c_2 \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies(c_1log_b(n)\leq log_a(n)\leq c_2\log_b(n))} $$
            \end{quote}
            {\bf Proof:} 
            \begin{pindent}
            	Let $c_1' = a$ Then $c' \in \R^+$\\
            	let $B'=1,$ Then $B' \in \N$\\
        
                \begin{assumption}{$(n\in \N) \land (n \geq B')$}
                Assume there is a least bound.\\
        		Then $ a\log_b(n)> \log_a(n) $\just{Take $a$ sufficiently large.}\\
        		But $ a\land 1 $ \just{Given.}\\
        		Therefore, $ a\log_b(n)\leq \log_a(n) $\\
        		We reach a contradiction.\just{$a$ cannot be strictly greater than 1 and 1.}
                \end{assumption}
                Then ${\exists c_1\in \R^+,\exists c_2 \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \not \implies(c_1log_b(n)\leq log_a(n)\leq c_2\log_b(n))}$
                
                % $ \ \forall n \in \Z,\ \sum_{1}^{i} (2n-1) \equiv n^2  $
            \end{pindent}
            \medskip
                
	\end{enumerate}
    \item
    Consider the following formal definition of $\Theta(f)$:
    \begin{quote} 
        $$\Theta(f) = {g: \N \rightarrow \R^+ |\exists c_1\in \R^+,\exists c_2 \in \R^+, \exists B \in \N, \forall n \in \N, (n \geq B) \implies(c_1f(n)\leq g(n)\leq c_2f(n)}) $$
    \end{quote}
    {\bf Proof:}
    \begin{pindent}

            \begin{assumption}{$\log_a(n), a \in \R^+, n \in \N$}
			Then there are two possible lower bounds for a worst-case logarithms:\\ $[( \log_b(n)\land(b\leq a)] \lor [((f(n)=c) \land (c \leq a))], b \in \R^+, c \in \N$
            \end{assumption}
            The first set of functions with a lower bound on a worst-case logarithm are the constants where, c is less than the worst-case logarithms base. The second set of functions with a lower bound on a worst-case logarithm are the logarithmic functions where, the base b is less than or equal to the worst-case logarithms base.
        \end{pindent}
        \medskip
       


\end{enumerate}

\noindent
\rule{\textwidth}{.5pt}

\end{document}
